package org.blogwu.learn.leetcode.二叉树;


import org.blogwu.learn.algorithm.树.二叉搜索树.printer.BinaryTrees;

public class _450_删除二叉搜索树中的节点 {

    public static void main(String[] args) {
        // [4,2,5,1,3]
//        {10,5,25,1,8,null,null,null,null,6}
//        Integer[] sz = {10,5,25,null,null,16,32,null,null,null,null,14,30,null,null,null,null,null,null,null,null,null,null,null,null,18};
        Integer[] sz = {8, 0, 31, null, 6, 28, 45, 4, 7, 25, 30, 32, 49, 2, 5, null, null, 9, 26, 29, null, null, 42, 47, null, null, 3, null, null, null, 12, null, 27, null, null, 41, 43, 46, 48, null, null, 10, 19, null, null, 33, null, null, 44, null, null, null, null, null, 11, 18, 20, null, 37, null, null, null, null, 14, null, null, 22, 36, 38, 13, 15, 21, 24, 34, null, null, 39, null, null, null, 16, null, null, 23, null, null, 35, null, 40, null, 17};
        TreeNode root = TreeNode.convert(sz);

        BinaryTrees.print(root);
        System.out.println("");
        root = deleteNode(root, 1);
        BinaryTrees.print(root);
        System.out.println("");
        TreeNode root1 = TreeNode.convert(sz);
        System.out.println("");
        Solution_450 solution_450 = new Solution_450();
        solution_450.deleteNode(root1, 1);
        BinaryTrees.print(root1);
    }

    public static void main1(String[] args) {
        TreeNode treeNode = new TreeNode();
        Integer[] ints = new Integer[]{
                10, 25, 16, 32, 30, 14, 19, 15, 17
        };
        for (int i = 0; i < ints.length; i++) {
            treeNode.add(ints[i]);
        }
        BinaryTrees.print(treeNode.getRoot());
        Solution_450 solution_450 = new Solution_450();
        treeNode = solution_450.deleteNode(treeNode.getRoot(), 19);
        System.out.println("");
        System.out.println("-----");
        BinaryTrees.print(treeNode.getRoot());

    }


    public static void main3(String[] args) {
        TreeNode treeNode = new TreeNode();
        Integer[] ints = new Integer[]{
//                11, 24, 7, 4, 25, 21, 6, 20, 30
//                80, 68, 91, 87, 75, 16, 33, 81, 83, 25, 97, 67, 45, 24, 65, 100, 61,69,70,77,78,76
//                5,3,6,2,4,7
//                0
//                3,1,4,2
//                5,3,6,2,4,7
//                10,25,16,32,30,14,17,15
                10, 25, 16, 32, 30, 14, 19, 15, 17
        };
        for (int i = 0; i < ints.length; i++) {
            treeNode.add(ints[i]);
        }
        BinaryTrees.print(treeNode.getRoot());
        treeNode = deleteNode(treeNode.getRoot(), 19);
        System.out.println("");
        System.out.println("-----");
        BinaryTrees.print(treeNode.getRoot());

    }


    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;
        // 先找到改节点
        TreeNode parent = null;
        TreeNode node = root;
        while (node != null) {
            int cmp = key - node.val;
            if (cmp == 0) {
                break;
            } else if (cmp > 0) {
                // 如果为null了，肯定是没找到
                parent = node;
                node = node.right;
            } else if (cmp < 0) {
                parent = node;
                node = node.left;
            }
        }
        if (node == null) return root;
        // 判断是否是 叶子节点
        if (node.left == null && node.right == null) {
            if (parent == null) {
                node = null;
                return null;
            } else {
                if (parent.left == node) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }
            node = null;
            return root;
        }
        // 剩下情况就是度数为1的节点
        if ((node.left != null || node.right != null) && !(node.left != null && node.right != null)) {
            if (node.left != null) {
                TreeNode tt = node.left;
                node.val = node.left.val;
                node.left = tt.left;
                node.right = tt.right;
            } else {
                TreeNode tt = node.right;
                node.val = node.right.val;
                node.left = tt.left;
                node.right = tt.right;
            }
            return root;
        }

        TreeNode frontNode = node.left;
        TreeNode frontNodeParent = node;
        // 寻找前驱节点
        while (frontNode != null) {
            if (frontNode.right != null) {
                frontNodeParent = frontNode;
            }
            if (frontNode.right == null) {
                break;
            }
            frontNode = frontNode.right;
        }

        // 非叶子节点 度数为2的节点  前驱替换当前
        if (node.left != null && node.right != null) {
            node.val = frontNode.val;
            // 这种是顶层节点
            if (frontNode != node.left) {
                // 先交换变量
                frontNodeParent.right = null;
                if (frontNodeParent.left == null) {
                    frontNodeParent.left = frontNode.left;
                } else {
                    frontNodeParent.right = frontNode.left;
                }
            } else {
                node.left = frontNode.left;
            }
            frontNode = null;
        }
        return root;
    }


    /**
     * 添加元素
     */
    public static void add(int val) {
        // 初始化根节点
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        // 非第一个节点
        TreeNode node = root;
        TreeNode parent = root;
        int cmp = 0;
        // 一直遍历
        while (node != null) {
            cmp = val - node.val;
            // 保存父节点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {  // 相等
                node.val = val;
                return;
            }
        }
        // 插入节点
        TreeNode newNode = new TreeNode(val);
        // 保存父节点
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
    }

    static TreeNode root = null;
}
